home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / bin_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  8.0 KB  |  318 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  bin_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #ifndef LEDA_BIN_TREE_H
  18. #define LEDA_BIN_TREE_H
  19.  
  20. //------------------------------------------------------------------------------
  21. //
  22. // bin_tree  
  23. //
  24. //     base class for all leaf oriented binary trees in LEDA
  25. //
  26. // Ijon Tichy  (1993)
  27. //
  28. //------------------------------------------------------------------------------
  29.  
  30.  
  31. #include <LEDA/basic.h>
  32.  
  33.  
  34. class bin_tree;
  35. class bin_tree_node;
  36.  
  37. typedef bin_tree_node* bin_tree_item;
  38.  
  39. typedef void (*DRAW_BIN_NODE_FCT)(double,double,void*,int);
  40. typedef void (*DRAW_BIN_EDGE_FCT)(double,double,double,double);
  41.  
  42.  
  43. //------------------------------------------------------------------------------
  44. // class bin_tree_node 
  45. //------------------------------------------------------------------------------
  46.  
  47. class bin_tree_node
  48. {  
  49.    friend class bin_tree;
  50.    friend class avl_tree;
  51.    friend class bb_tree;
  52.    friend class rb_tree;
  53.    friend class rs_tree;
  54.  
  55.  
  56.    GenPtr   k;              // key
  57.    GenPtr   i;              // info
  58.  
  59.    bin_tree_node* child[2]; // node: left and right child
  60.                             // leaf: successor and predecessor
  61.  
  62.    bin_tree_node* parent;   // pointer to parent
  63.  
  64.    bin_tree_node* corr;     // leaf: pointer to corresponding inner node
  65.                             // node: nil
  66.  
  67.    int   bal;               // rebalancing data
  68.  
  69.  
  70.    public:
  71.  
  72.  
  73.    bin_tree_node(GenPtr key, GenPtr inf, int b)
  74.    { k = key;
  75.      i = inf; 
  76.      bal = b;
  77.     }         
  78.  
  79.    bin_tree_node() { }         
  80.  
  81.    bin_tree_node(bin_tree_node* p)
  82.    { k = p->k;
  83.      i = p->i ;
  84.      bal = p->bal;
  85.     }         
  86.  
  87.    bool is_node()   { return (corr == nil);  }
  88.    bool is_leaf()   { return (corr != nil); }
  89.  
  90.    void set_bal(int x) { bal = x; }
  91.    int  get_bal()      { return bal; }
  92.  
  93.  
  94.    LEDA_MEMORY(bin_tree_node)
  95.  
  96. };
  97.  
  98.  
  99.  
  100. //------------------------------------------------------------------------------
  101. // class bin_tree
  102. //------------------------------------------------------------------------------
  103.  
  104. class bin_tree
  105. { 
  106.   protected:
  107.  
  108.   enum { left=0, right=1 };
  109.  
  110.   bin_tree_node ROOT;      // "super root" to avoid special cases in rotations
  111.                            // ROOT.child[left] points to real root node
  112.                            // ROOT.child[right] points to leftmost leaf
  113.   int count;            
  114.  
  115.  
  116.   // functions depending on used rebalancing method
  117.   // will be defined in derived classes (rb_tree, avl_tree, ...)
  118.  
  119.   virtual int leaf_balance() { return 0; }  // default balance value for leaves
  120.   virtual int node_balance() { return 0; }  // inner nodes
  121.   virtual int root_balance() { return 0; }  // root node
  122.  
  123.   virtual void insert_rebal(bin_tree_node*)   {}
  124.   virtual void del_rebal(bin_tree_node*, bin_tree_node*) {}
  125.  
  126.  
  127.  
  128.  
  129.   // other protected member functions
  130.  
  131.   bin_tree_node*& min_ptr() const 
  132.                            { return (bin_tree_node*&)ROOT.child[right];}
  133.  
  134.   void rotation(bin_tree_node*, bin_tree_node*, int);
  135.   void double_rotation(bin_tree_node*, bin_tree_node*, bin_tree_node*, int);
  136.  
  137.   void del_tree(bin_tree_node*);
  138.  
  139.   bin_tree_node* int_search(GenPtr) const;
  140.   bin_tree_node* search(GenPtr) const;
  141.   bin_tree_node* copy_tree(bin_tree_node*,bin_tree_item&) const;
  142.  
  143.  
  144.  
  145.   // functions depending on actual key type
  146.   // will be defined in dictionary and sortseq templates
  147.  
  148.   virtual int cmp(GenPtr x, GenPtr y) const { return compare(x,y); }
  149.  
  150.   virtual void clear_key(GenPtr&) const { }
  151.   virtual void clear_inf(GenPtr&) const { }
  152.   virtual void clear_iinf(GenPtr&)const { }
  153.  
  154.   virtual void copy_key(GenPtr&)  const { }
  155.   virtual void copy_inf(GenPtr&)  const { }
  156.  
  157.   virtual void print_key(GenPtr) const { }
  158.   virtual void print_inf(GenPtr) const { }
  159.  
  160.   virtual int  int_type() const { return 0; }
  161.  
  162.   //bin_tree_node* item(void* p) const { return (bin_tree_node*)p; }
  163.  
  164.  
  165. public:
  166.  
  167.   bin_tree_node* item(void* p) const { return (bin_tree_node*)p; }
  168.  
  169.   bin_tree_node*& root() const 
  170.                            { return (bin_tree_node*&)ROOT.child[left]; }
  171.  
  172.  
  173.   bin_tree_node* cyclic_succ(bin_tree_node* p) const { return p->child[right]; }
  174.   bin_tree_node* cyclic_pred(bin_tree_node* p) const { return p->child[left]; }
  175.  
  176.   bin_tree_node* succ(bin_tree_node* p) const
  177.   { return (p->child[right] == min_ptr()) ? 0 : p->child[right]; }
  178.  
  179.   bin_tree_node* pred(bin_tree_node* p) const
  180.   { return (p == min_ptr())  ?  0 : p->child[left] ; }
  181.  
  182.   bin_tree_node* first_item()  const               { return min_ptr(); }
  183.   bin_tree_node* next_item(bin_tree_node* p) const { return succ(p); }
  184.  
  185.   bin_tree_node* min() const { return min_ptr(); }
  186.   bin_tree_node* max() const { return (count>0) ? min_ptr()->child[left] : 0; }
  187.  
  188.  
  189.   bin_tree& conc(bin_tree&);
  190.   void split_at_item(bin_tree_node*,bin_tree&,bin_tree&);
  191.   void reverse_items(bin_tree_node*,bin_tree_node*);
  192.  
  193.  
  194.   bin_tree_node* insert(GenPtr,GenPtr,GenPtr=0);
  195.   bin_tree_node* insert_at_item(bin_tree_node*,GenPtr,GenPtr,GenPtr=0);
  196.   bin_tree_node* lookup(GenPtr) const;
  197.   bin_tree_node* locate(GenPtr) const;
  198.   bin_tree_node* locate_succ(GenPtr) const; 
  199.   bin_tree_node* locate_pred(GenPtr) const; 
  200.  
  201.   GenPtr   key(bin_tree_node* p)  const { return  p->k; }
  202.   GenPtr   inf(bin_tree_node* p)  const { return  p->i; }
  203.   GenPtr&  info(bin_tree_node* p) const { return  p->i; }
  204.  
  205.   void del(GenPtr);
  206.   void del_item(bin_tree_node* p);
  207.   void change_inf(bin_tree_node*,GenPtr);
  208.  
  209.   void clear();
  210.  
  211.   int size()   const { return count; } 
  212.   int empty()  const { return root() ? false : true ; }
  213.  
  214.  
  215.  
  216.   // construction, assignment, destruction
  217.  
  218.   bin_tree() {  count = 0; root() = nil; min_ptr() = nil; }
  219.  
  220.   bin_tree(const bin_tree&);
  221.   bin_tree& operator=(const bin_tree&);
  222.  
  223.   virtual ~bin_tree() { clear(); }
  224.  
  225.  
  226.  
  227.   // additional operations used by range and segment trees
  228.  
  229.   virtual void propagate_modification(int, GenPtr, GenPtr) {}
  230.  
  231.   bin_tree_node* l_child(bin_tree_node* p) const
  232.   { return p->is_leaf() ? 0 : p->child[left]; }
  233.  
  234.   bin_tree_node* r_child(bin_tree_node* p) const
  235.   { return p->is_leaf() ? 0 : p->child[right]; }
  236.  
  237.   int is_inner(bin_tree_node* p)  const
  238.   { return p->corr == 0; }
  239.  
  240.   bin_tree_node* parent(bin_tree_node* p)  const
  241.   { return (p==root()) ? 0 : p->parent; }
  242.  
  243.  
  244.   // miscellaneous
  245.  
  246.   void draw(DRAW_BIN_NODE_FCT, DRAW_BIN_NODE_FCT, DRAW_BIN_EDGE_FCT, 
  247.             bin_tree_node*, double, double, double, double, double);
  248.  
  249.   void draw(DRAW_BIN_NODE_FCT, DRAW_BIN_NODE_FCT, DRAW_BIN_EDGE_FCT, 
  250.             double, double, double, double);
  251.  
  252.   void print() const;
  253.   void print_tree(bin_tree_node*,int) const;
  254.  
  255. };
  256.  
  257.  
  258.  
  259. inline void bin_tree::rotation(bin_tree_node* p,bin_tree_node* q, int dir)
  260. { bin_tree_node* r = q->child[1-dir];
  261.   bin_tree_node* x = p->parent;
  262.   p->child[dir] = r;
  263.   q->child[1-dir] = p;
  264.   p->parent = q;
  265.   r->parent = p;
  266.   if (p == x->child[left])
  267.      x->child[left] = q;
  268.   else
  269.      x->child[right] = q;
  270.   q->parent = x;
  271.  
  272.   propagate_modification(4,p,r);
  273.   propagate_modification(5,q,p);
  274.   if( x!=&ROOT )
  275.     propagate_modification(6,x,q);
  276.  }
  277.  
  278.  
  279. inline void bin_tree::double_rotation(bin_tree_node* p, bin_tree_node* q, 
  280.                                       bin_tree_node* r, int dir1)
  281. { int dir2 = 1-dir1;
  282.   bin_tree_node* s = r->child[dir1];
  283.   bin_tree_node* t = r->child[dir2];
  284.   bin_tree_node* x = p->parent;
  285.   p->child[dir1] = t;
  286.   q->child[dir2] = s;
  287.   r->child[dir1] = q;
  288.   r->child[dir2] = p;
  289.   p->parent = r;
  290.   q->parent = r;
  291.   s->parent = q;
  292.   t->parent = p;
  293.  
  294.   if (p == x->child[left])
  295.      x->child[left] = r;
  296.   else
  297.      x->child[right] = r;
  298.  
  299.   r->parent = x;
  300.  
  301.   propagate_modification(7,p,t);
  302.   propagate_modification(8,q,s);
  303.   propagate_modification(9,r,p);
  304.   propagate_modification(10,r,q);
  305.   if( x!=&ROOT )
  306.     propagate_modification(11,x,r);
  307. }
  308.  
  309.  
  310.  
  311. // dummy I/O and cmp functions
  312.  
  313. inline void Print(const bin_tree&,ostream&) { }
  314. inline void Read(bin_tree&, istream&) { }
  315. inline int  compare(const bin_tree&,const bin_tree&) { return 0; }
  316.  
  317. #endif
  318.